package class5;

import common.ListNode;
import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * 从前序与中序遍历序列构造二叉树
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * <p>
 * 先序：1	2	4	5	3	6	7
 * 中序：4	2	5	1	6	3	7
 * 下标：0   1   2   3   4   5   6
 * <p>
 * 题目思路:
 */
public class Code05_BuildTree {
    public static void main(String[] args) {
        int[] pre = new int[]{1, 2, 4, 5, 3, 6, 7};
        int[] ins = new int[]{4, 2, 5, 1, 6, 3, 7};
        TreeNode root = buildTree(pre, ins);
        System.out.println(root);
    }

    public static TreeNode buildTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        HashMap<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            inorderMap.put(in[i], i);
        }
//        return f(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return g(pre, 0, pre.length - 1, in, 0, in.length - 1,inorderMap);
    }

    // 有一个树，先序结果是pre[L1...R1],中序结果是in[L2...R2]
    // 请建除整棵树的返回头
    public static TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
        // 边界限制
        if (L1 > R1) return null;
        // 只剩一个节点时，只返回一个节点
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        /**
         * 1.找到先序的头，在中序数组的位置
         * + 先序：[L1.......R1]
         * + 中序：[L2...x...R2]
         * 其中 L1 就是头节点，在中序的x位置, 因此 x 需要从 L2 开始向右找
         */
        // 初始化为L2的首节点
        int find = L2;
        // 没找到就自增

        while (in[find] != pre[L1]) {
            find++;
        }
        /**
         * 右边界的值: L1 + find -L2;
         *
         * find:这个偏差值的作用是帮助我们正确找到前序遍历中当前节点的位置，并且根据中序遍历的位置来决定它的左右子树。
         * 偏差值的计算实际上就是在解决“当前节点属于哪部分”的问题。通过前序遍历和中序遍历的配合，我们可以不断地拆解问题，最终构建整个二叉树。
         */
        head.left = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
        head.right = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
        return head;
    }

    // 有一个树，先序结果是pre[L1...R1],中序结果是in[L2...R2]
    // 请建除整棵树的返回头
    public static TreeNode g(int[] pre, int L1, int R1, int[] in, int L2, int R2, Map<Integer, Integer> integerMap) {
        // 边界限制
        if (L1 > R1) return null;
        // 只剩一个节点时，只返回一个节点
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        /**
         * 1.找到先序的头，在中序数组的位置
         * + 先序：[L1.......R1]
         * + 中序：[L2...x...R2]
         * 其中 L1 就是头节点，在中序的x位置, 因此 x 需要从 L2 开始向右找
         */
        int find = integerMap.get(pre[L1]);

        /**
         * 右边界的值: L1 + find -L2;
         *
         * find:这个偏差值的作用是帮助我们正确找到前序遍历中当前节点的位置，并且根据中序遍历的位置来决定它的左右子树。
         * 偏差值的计算实际上就是在解决“当前节点属于哪部分”的问题。通过前序遍历和中序遍历的配合，我们可以不断地拆解问题，最终构建整个二叉树。
         */
        head.left = g(pre, L1 + 1, L1 + find - L2, in, L2, find - 1,integerMap);
        head.right = g(pre, L1 + find - L2 + 1, R1, in, find + 1, R2,integerMap);
        return head;
    }
}
